import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    //组合总数
    public List<List<Integer>> ret;
    public List<Integer> path;
    public int t;
    public int[] nums;
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        ret = new ArrayList<>();
        path = new ArrayList<>();
        nums = candidates;
        Arrays.sort(nums);
        t = target;
        dfs(0, 0);
        return ret;
    }
    public void dfs(int index, int sum){
        //递归出口
        if(sum == t){
            ret.add(new ArrayList<>(path));
            return;
        }
        //剪枝
        if(sum > t || index == nums.length){
            return;
        }

        for(int k = 0; k * nums[index] + sum <= t; k++){
            if(k != 0) {
                path.add(nums[index]);
            }
            dfs(index + 1, sum + k * nums[index]);

        }
        for(int k = 1; k * nums[index] + sum <= t; k++){
            path.remove(path.size() - 1);
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {2, 3, 6, 7};
        solution.combinationSum(nums, 7);
    }
}